前言

昨天我們介紹了Lamport Logical Clock可以幫助我們找出分散式系統裡的Causality關係，但是有其缺點，
那就是雖然兩個event是平行發生無法比較先後，但是Lamport timestamp會顯示兩著有因果關係，也就是說因為 t1 < t2，所以在此方法下，我們會以為e1 happened before e2，但其實不然。
也就是: L(e)<L(e’) <=!=> e→ e’

Vector Clock

我們希望能夠在定位事件的先後順序時，仍能保留Partial Order的資訊，也就是兩個事件是平行發生並不會被強制規定先後。

換句話說，如果兩個事件無法排定先後，那就讓他們保持無法比較，也因此我們可以找出 Concurrent Events。這邊的Concurrent Events不是針對同一個物件的updates，而是真的完全沒有因果關係不重疊的兩個平行事件。

例如:
UserA register -> UserA login -> order -> buy
UserB register
UserA,B的註冊很明顯可以是平行事件，甚至無因果關係

前面Lamport Clock讓每個Node只存一個Logical Clock timestamp。現在我們讓N個Nodes，每一個Node都存有N個Logical Clock timestamp，形成一個Vector。

對Nodei儲存的Vector Vi: Vi = (t0, t1, t2, ..., tN)

也因此每個event e夾帶的timestamp，就是此時該Nodei的Vector timestamp Vi。

Vector Clock 演算法

1. 初始化每個Nodei的Vi裡的每個time都為0
2. 對Nodei，發生一個事件，則 Vi[ti]+1
3. 對Nodei，發生一個發送事件，則 Vi[ti]+1，並在event中夾帶該Vector Time
4. 對Nodej，發生一個接收事件，則 Vj[ti] = Vi[ti]且Vj[tj] = Max(Vj[tj], Vi[ti])+1。

比較:

1. V = V' <=> V[j] = V’[j] for j = 1, 2, ..., N
2. V ≤ V' <=> V[j] ≤ V’[j] for j = 1, 2, ..., N
3. V < V' <=> V ≤ V’ ∧ V ≠ V’

則對比之前的Lamport Logical Clock圖

我們現在可以解決event e跟c為平行無前後關係的事件，在Vector Clock中我們可以決定並保留他們是平行的。因為Vector中的每個值並不是全部大於或是全部小於。

Vector Clock 小結

1. 也就是說利用Vector Clock，我們仍然可以找出Causality關係: e → e’ <=> V(e) < V(e')
2. 同時我們可以保留真的是平行發生且沒關聯的事件: If V(e) ≰ V(e') and V(e') ≰ V(e), then e ∥ e'

例如: (2,1,0,4) ∥ (2,3,0,2)

Vector Clock 討論

到這邊我們似乎解決了時間飄移、Versioning與Event Ordering的問題。
但是，這是理論上的，什麼意思呢？
我們回到實作來想想，這些N個processes/nodes要在一開始初始化一個vector裡面有N個t1~tn logical time。
這是一個分散式系統耶

1. 他們怎麼知道總共有N個呢？如果中間有Node永遠消失了(系統管理員更改配置)？也就是說這個系統要能夠知道 Membership。
2. 另一個比較小的問題是，每個Node要存一個Vector有N個值，如果我的分散式系統有很多個Node散落世界各地的中心，這個Vector光用想的就佔很大的空間？

總結

分散式系統就是這麼的麻煩！
不只是每個領域都可以生出一堆理論上的研究，且彼此相關聯。
當理論進入實作時又是一堆研究加系統的設計經驗。

因此接下來我們會舉幾個例子來看Vector Clock怎麼應用並解決剛剛的問題吧。